package LearnAlgorithm.i_递归进阶andDFSand剪枝and回溯;

import java.util.ArrayList;
import java.util.Arrays;


public class f全排列by回溯 {
	ArrayList<String> res = new ArrayList<String>();
	public static void main(String[] args) {
		f全排列by回溯 test = new f全排列by回溯();
		ArrayList<String> res1 = test.UseGetPermutationByRecall("ABC");
		System.out.println(res1);
	}
	
	/**
	 * 回溯前置使用方法
	 * @param s
	 * @return
	 */
	public ArrayList<String> UseGetPermutationByRecall(String s) {
		char[] arr = s.toCharArray();
		Arrays.sort(arr);
		getPermutationByRecall(arr, 0);
		return res;
	}
	
	/**
	 * 回溯核心语句
	 * 看不懂就死记硬背
	 * 这里确实很抽象
	 * @param arr
	 * @param current
	 */
	public void getPermutationByRecall(char[] arr, int current) {
		if (current == arr.length) {
			res.add(new String(arr));
			return;
		}
		for (int i = current; i < arr.length; i++) {//从k位开始的每个字符都尝试放在新排列的k这个位置
			swap(arr, current, i);//把后面每个字符换到k位
			getPermutationByRecall(arr, current + 1);
			swap(arr, current, i);//回溯
		}
	}
	
	/**
	 * 帮助方法
	 * 交换数组元素
	 * @param arr
	 * @param x
	 * @param y
	 */
	public void swap(char[] arr, int x, int y) {
		char temp = arr[x];
		arr[x] = arr[y];
		arr[y] = temp;
	}
}
